package other;

import java.util.ArrayList;
import java.util.List;

public class D230907 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    // 二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 分别获取根结点到 p, q 的路径
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode res = null;
        // 对比两条路径,最后一个相等的结点,就是最近的公共祖先
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            if (path_p.get(i) == path_q.get(i)) {
                res = path_p.get(i);
            } else {
                break;
            }
        }
        return res;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (node.val < target.val) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        // p 或 q 也要加入路径中,因为可能是答案
        path.add(node);
        return path;
    }
}
